package com.formula.datastructure.exercise.sort.adv;

import com.formula.datastructure.util.DataUtil;

/**
 * 心得体会
 * #1 先写出插入排序
 * #2 写出一个step的for语句
 * #3 涉及步长, 一般就是插入排序中的1, 替换为step
 * #5 时间复杂度: 最坏情况, 最好情况
 */
// 不需要申明辅助数组
public class ShellSort {

    /**
     * 经验:
     * #4
     */
    public Integer[] sort(Integer[] input) {
        for (int step = input.length / 2; step >= 1; step = step / 2) {
            // 这里面就是插入排序, 但是带步长
            for (int i = step; i < input.length; i = i + step) {
                Integer insert = input[i];
                int idx = i;
                for (int j = i - step; j >= 0; j = j - step) {
                    // #5 这里是和insert比
                    if (insert < input[j]) {
                        // #4 记住修改这里的步长
                        input[j + step] = input[j];
                        idx = j;
                    } else {
                        break;
                    }
                }
                // 如果没有被替换
                if (idx != i) {
                    input[idx] = insert;
                }
            }
        }
        return input;
    }

    public static void main(String[] args) {
        ShellSort shell = new ShellSort();
        Integer[] array = DataUtil.genUniqueArray(12, 50);
        DataUtil.printIndex(12);
        DataUtil.printArray(array);
        DataUtil.printArray(shell.sort(array));
    }
}
